package weighteddirectedgraph;

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class WeightedDirectedGraph<ItemType, CostType> 
{
	private Map<ItemType, Vertex> vertices;

	public WeightedDirectedGraph()
	{
		vertices = new LinkedHashMap<ItemType, Vertex>();
	}

	public void addItem(ItemType item)
	{
		Vertex v = new Vertex(item);
		vertices.put(item, v);
	}

	public void addEdge(ItemType from, ItemType to, CostType cost)
	{
		assert vertices.get(from) != null;
		assert vertices.get(to)   != null;

		Vertex my_To   = vertices.get(to);
		Vertex my_From = vertices.get(from);
		if(my_To != null && my_From != null)
		{
			if(!my_From.getBuurKnopen().contains(to))
				my_From.addZijde(my_To, cost);
		}
	}

	public List<ItemType> getNeighbourValues(ItemType item)
	{
		ArrayList<ItemType> result = new ArrayList<ItemType>();
		for(Vertex v : vertices.get( item ).getBuurKnopen())
		{
			result.add(v.getItem());
		}
		return result;
	}

	public CostType getCost(ItemType from, ItemType to)
	{
		Vertex my_From = vertices.get(from);
		Vertex my_To = vertices.get(to);
		return my_From.getCost(my_To);
	}

	public ArrayList<ItemType> bezoekDepthFirst(ItemType startItem)
	{
		ArrayList<ItemType> visited = new ArrayList<ItemType>();
		return bezoekDepthFirst(startItem, visited);
	}

	private ArrayList<ItemType> bezoekDepthFirst(ItemType startItem, ArrayList<ItemType> visited)
	{
		Vertex start = vertices.get(startItem);		
		visited.add(start.getItem());

		for(Vertex v : start.getBuurKnopen())
		{
			if(!visited.contains(v))
				bezoekDepthFirst(v.getItem(), visited);
		}		
		return visited;
	}

	public ArrayList<ItemType> bezoekBreadthFirst(ItemType startItem)
	{	
		ArrayList<ItemType> visited = new ArrayList<ItemType>() ;
		ArrayList<Vertex> my_queue = new ArrayList<Vertex>() ;

		Vertex start = vertices.get(startItem);
		visited.add( start.getItem() );
		my_queue.add( start );

		return bezoekBreadthFirst( my_queue,  visited );
	}

	private ArrayList<ItemType> bezoekBreadthFirst(ArrayList<Vertex> queue, ArrayList<ItemType> visited)
	{
		if (queue.isEmpty())
			return visited;

		Vertex current = queue.get( 0 );

		if(!visited.contains( current.getItem() ))
			visited.add( current.getItem() );

		for(ItemType v: getNeighbourValues(current.getItem()))
		{
			queue.add(vertices.get( v ));
		}
		queue.remove( 0 );

		// stop alle buren in de queue (als ze er nog niet in zitten)
		return bezoekBreadthFirst( queue,  visited );
	}

	private class Vertex
	{
		private ItemType my_Item;
		private LinkedHashMap<Vertex, CostType> neighbors;

		public Vertex(ItemType item)
		{
			my_Item = item;
			neighbors = new LinkedHashMap<Vertex, CostType>();
		}

		public void addZijde(Vertex to, CostType cost)
		{
			neighbors.put(to, cost);
		}

		public List<Vertex> getBuurKnopen()
		{
			ArrayList<Vertex> buren = new ArrayList<Vertex>();
			for(Vertex v: neighbors.keySet())
			{
				buren.add( v );
			}	
			return buren;
		}

		public ItemType getItem()
		{
			return my_Item;
		}


		public CostType getCost(Vertex to)
		{
			return neighbors.get(to);
		}
	}
}
